1. Field of the Invention
The present invention relates generally to matrix-valued methods and apparatus for processing signals. More particularly, the invention relates to matrix-valued Fast Fourier Transform (FFT) and matrix-valued Inverse Fast Fourier Transform (IFFT) methods and processors.
2. Introduction and Notation
This invention deals with matrix-valued functions, variables, quantities, algorithms and systems as opposed to scalar-valued functions, variables, quantities, algorithms and systems. In order to describe these functions, variables, quantities, algorithms and systems, the following notation is adopted throughout this disclosure:    Scalar functions and variables are denoted in lower case letters (e.g. x, y, a).    Letters k, n, m, r, p, q, K, N, M are used to denote integer variables.    A vector of scalar quantities is denoted by lower case, bold letters (e.g. x, a).    A matrix of scalars is denoted by upper case, bold, Times Roman font (e.g. X, A).    A matrix of matrices is denoted by upper case, bold, Euclid font (e.g. W, H).    An identity matrix of a given size is denoted by I. That is
  I  =      [                            1                          0                          ⋯                          0                                      0                          1                          ⋯                          0                                      ⋮                          ⋮                          ⋰                          ⋮                                      0                          0                          ⋯                          1                      ]      A diagonal matrix with elements
  Λ  =      [                                        λ            1                                    0                          ⋯                          0                                      0                                      λ            2                                    ⋯                          0                                      ⋮                          ⋮                          ⋰                          ⋮                                      0                          0                          ⋯                                      λ            n                                ]  is denoted by diagonal {λ1, λ2, . . . , λn}.    An all-zeros matrix or vector is denoted by 0.    The symbol (.)⊥ is used to denote the complex conjugate transpose of a matrix or a vector.    The symbol j is used to represent the imaginary number √{square root over (−1)}.    |x| means norm of the vector x.    (p-m) mod M means to divide (p-m) by M and retain the remainder only.
In order to recognize the value and contributions of the present invention, it is important to understand the difference between the matrix form of an algorithm involving scalar variables and a matrix-valued algorithm involving matrix variables. Consider, for example, the following relationships between two known scalars {y1, y2} and two unknown scalars {x1, x2}a11x12+a12x22+b11x1+b12x2=y1a21x12+a22x22+b21x1+b22x2=y2  (1)
The matrix form of the above scalar-valued equations can be written as
                                                                        [                                                                                                    a                        11                                                                                                            a                        12                                                                                                                                                a                        21                                                                                                            a                        22                                                                                            ]                            ⁡                              [                                                                                                    x                        1                        2                                                                                                                                                x                        2                        2                                                                                            ]                                      +                                          [                                                                                                    b                        11                                                                                                            b                        12                                                                                                                                                b                        21                                                                                                            b                        22                                                                                            ]                            ⁡                              [                                                                                                    x                        1                                                                                                                                                x                        2                                                                                            ]                                              =                      [                                                                                y                    1                                                                                                                    y                    2                                                                        ]                          ⁢                                  ⁢        or                            (        2        )                                                      A            ⁡                          [                                                                                          x                      1                      2                                                                                                                                  x                      2                      2                                                                                  ]                                +                      B            ⁡                          [                                                                                          x                      1                                                                                                                                  x                      2                                                                                  ]                                      =                  [                                                                      y                  1                                                                                                      y                  2                                                              ]                                    (        3        )            
Observe that all the matrices and vectors are scalar-valued quantities. In contrast, consider a similar relationship between two known matrices {Y1, Y2} and two unknown matrices {X1, X2},A11X12+A12X22+B11X1+B12X2=Y1A21X12+A22X22+B21X1+B22X2=Y2  (4)
The preceding matrix-valued equations can be written in a compact way as
                                                                        [                                                                                                    A                        11                                                                                                            A                        12                                                                                                                                                A                        21                                                                                                            A                        22                                                                                            ]                            ⁡                              [                                                                                                    X                        1                        2                                                                                                                                                X                        2                        2                                                                                            ]                                      +                                          [                                                                                                    B                        11                                                                                                            B                        12                                                                                                                                                B                        21                                                                                                            B                        22                                                                                            ]                            ⁡                              [                                                                                                    X                        1                                                                                                                                                X                        2                                                                                            ]                                              =                      [                                                                                Y                    1                                                                                                                    Y                    2                                                                        ]                          ⁢                                  ⁢        or                            (        5        )                                                      A            ⁡                          [                                                                                          X                      1                      2                                                                                                                                  X                      2                      2                                                                                  ]                                +                      B            ⁡                          [                                                                                          X                      1                                                                                                                                  X                      2                                                                                  ]                                      =                  [                                                                      Y                  1                                                                                                      Y                  2                                                              ]                                    (        6        )            
Now, note that all the matrices and vectors in Eq.6 are matrix-valued objects. Although A and B of Eq.3 are matrices of scalars, A and B of Eq.6 are matrices of matrices. In other words, the fundamental mathematical unit of Eq.3 is a scalar entity whereas the fundamental mathematical unit of Eq.6 is a matrix entity. It is true that a vector of matrices (hereafter called a hyper-vector) and a matrix of matrices (hereafter called a hyper-matrix) can be treated as a matrix of scalars. However, as the dimensions of these vectors and matrices increase into the thousands, the computational methods and algorithms developed over the past centuries using the scalar framework fail to converge and as a result they yield unacceptable solutions.
On the other hand, the matrix-valued framework is particularly convenient for representations of higher-order systems with thousands of matrix-valued inputs and outputs. It is extremely efficient for finding accurate numerical solutions. Furthermore, the matrix-valued framework is a unique platform for introducing original concepts and developing new analysis and design techniques. It must be pointed out that the matrix-valued methods and algorithms are more general than those of the scalar based framework. Indeed, although the matrix-valued methods and algorithms reduce to their scalar-valued counterparts, the converse is not true. That is, the solution methods and algorithms of the scalar framework do not directly and readily extend to the realm of matrix-valued problems. For example, the concept of division is well established in the scalar domain. However, the division of two vectors or two matrices is not defined in the vector or matrix domain. Instead, the concept of matrix inverse must be used. These kinds of problems originating from a scalar perspective explain why the novel concepts and solution methods disclosed in this invention have been elusive until now.
3. Description of the Prior Art
In the prior art, serial information is processed in the form of scalar-valued signals. In such a system, a single variable function of time (discrete or continuous) is sufficient to describe how a particular characteristic of a data stream changes over a period of time. The most popular method for analyzing and solving signal processing problems is to utilize the properties of the scalar-valued Fourier transform. The Fourier transform is the main tool to represent signals in the frequency domain. To illustrate what is meant by the scalar-valued Fourier transform and emphasize the single variable nature of the prior art, consider a set of N samples of a discrete-time signal, {x(n), n=0,1,2, . . . , N−1}. Now, the conventional discrete Fourier transform (DFT) of x(n) is defined by the following expression
                                          f            ⁡                          (              k              )                                =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              ⅇ                                  -                                      j                    ⁡                                          (                                                                        2                          ⁢                          π                          ⁢                                                                                                          ⁢                          kn                                                N                                            )                                                                                                          ,                  k          =          0                ,        1        ,        2        ,        …        ⁢                                  ,                  N          -          1                                    (        7        )            where the symbol j represents the imaginary number √{square root over (−1)}. Note that N real data values (in the time domain) transform to N complex DFT values (in the frequency domain). Likewise, given a set of N discrete-frequency samples {f(k), k=0,1,2, . . . , N−1}, the conventional inverse discrete Fourier transform (IDFT) of f(k) is given by
                                          x            ⁡                          (              n              )                                =                                    1              N                        ⁢                                          ∑                                  k                  =                  0                                                  N                  -                  1                                            ⁢                                                f                  ⁡                                      (                    k                    )                                                  ⁢                                  ⅇ                                      j                    ⁡                                          (                                                                        2                          ⁢                          π                          ⁢                                                                                                          ⁢                          kn                                                N                                            )                                                                                                          ,                  n          =          0                ,        1        ,        2        ,        …        ⁢                                  ,                  N          -          1                                    (        8        )            
Since there is a common term, the above definitions are usually simplified by introducing the following symbol
                    w        =                  ⅇ                      -                          j              ⁡                              (                                                      2                    ⁢                    π                                    N                                )                                                                        (        9        )            
Note that w is a scalar-valued quantity and it is called twiddle factor in practice. Equations (7) and (8) can then be written in terms of the twiddle factor as
                                                        f              ⁡                              (                k                )                                      =                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                x                  ⁡                                      (                    n                    )                                                  ⁢                                  w                  kn                                                              ,                      k            =            0                    ,          1          ,          2          ,          …          ⁢                                          ,                      N            -            1                          ⁢                                  ⁢        and                            (        10        )                                                      x            ⁡                          (              n              )                                =                                    1              N                        ⁢                                          ∑                                  k                  =                  0                                                  N                  -                  1                                            ⁢                                                f                  ⁡                                      (                    k                    )                                                  ⁢                                  w                                      -                    kn                                                                                      ,                  n          =          0                ,        1        ,        2        ,        …        ⁢                                  ,                  N          -          1                                    (        11        )            
The DFT samples defined in Eq.7 can be expressed in matrix-vector form as
                                          [                                                                                f                    ⁡                                          (                      0                      )                                                                                                                                        f                    ⁡                                          (                      1                      )                                                                                                                                        f                    ⁡                                          (                      2                      )                                                                                                                    ⋮                                                                                                  f                    ⁡                                          (                                              N                        -                        1                                            )                                                                                            ]                    =                                    [                                                                    1                                                        1                                                        1                                                        ⋯                                                        1                                                                                        1                                                        w                                                                              w                      2                                                                            ⋯                                                                              w                                              N                        -                        1                                                                                                                                  1                                                                              w                      2                                                                                                  w                      4                                                                            ⋯                                                                              w                                              2                        ⁢                                                  (                                                      N                            -                            1                                                    )                                                                                                                                                          ⋮                                                        ⋮                                                        ⋮                                                        ⋰                                                        ⋮                                                                                        1                                                                              w                                              N                        -                        1                                                                                                                        w                                              2                        ⁢                                                  (                                                      N                            -                            1                                                    )                                                                                                                          ⋯                                                                              w                                                                        (                                                      N                            -                            1                                                    )                                                ⁢                                                  (                                                      N                            -                            1                                                    )                                                                                                                                ]                        ⁡                          [                                                                                          x                      ⁡                                              (                        0                        )                                                                                                                                                        x                      ⁡                                              (                        1                        )                                                                                                                                                        x                      ⁡                                              (                        2                        )                                                                                                                                  ⋮                                                                                                              x                      ⁡                                              (                                                  N                          -                          1                                                )                                                                                                        ]                                      ⁢                                  ⁢        or                            (        12        )                                f        =        Fx                            (        13        )            where x is the vector of N input samples and f is the vector of DFT transform samples and F is the N×N Fourier matrix. In a similar fashion, the IDFT relationships can be expressed in matrix-vector form asx=F−1f  (14)where F−1 is the inverse of the Fourier matrix. The important role that DFT plays in the analysis, synthesis, and implementation of digital signal processing algorithms is well known to those skilled in the art. See, for example, [1] “The Digital Signal Processing Handbook” edited by V. K. Madisetti and D. B. Williams, a CRC handbook published in cooperation with IEEE Press, 1998, ISBN 0-8493-8572-5, and [2] “Digital Signal Processing, A Practical Approach” by E. C. Ifeachor and B. W. Jervis, 2nd Edition, Prentice Hall, 2002, ISBN 0201-59619-9, which are incorporated herein by reference.
If the concept of dimension is expanded to include space, then many of the concepts and properties of DFT in one dimension can be extended to multi-dimensional signals. For example, to measure the frequency content of an image, a two-dimensional DFT analysis is employed by using the following equation
                                          f            ⁡                          (                                                k                  1                                ,                                  k                  2                                            )                                =                                    ∑                                                n                  1                                =                0                                                              N                  1                                -                1                                      ⁢                                          ∑                                                      n                    2                                    =                  0                                                                      N                    2                                    -                  1                                            ⁢                                                x                  ⁡                                      (                                                                  n                        1                                            ,                                              n                        2                                                              )                                                  ⁢                                  ⅇ                                      -                                          j2π                      ⁡                                              (                                                                                                                                            k                                1                                                            ⁢                                                              n                                1                                                                                                                    N                              1                                                                                +                                                                                                                    k                                2                                                            ⁢                                                              n                                2                                                                                                                    N                              2                                                                                                      )                                                                                                                                ,                                  ⁢                  0          ≤                      k            1                    ≤                                    N              1                        -            1                          ,                  0          ≤                      k            2                    ≤                                    N              2                        -            1                                              (        15        )            
Conversion of this equation to a sequence of two one-dimensional DFT is accomplished by noting that the exponential term can be factored into two terms. However, it is important to emphasize that, even though 2-dimensional data are being processed, the transform relationship of Eq.15 is still a scalar-valued algorithm in terms of its input x(n1, n2) and output f(k1, k2) samples. This scalar-valued formulation is also true for higher order dimensions as in 3-dimensional video processing.
Another generalization of the DFT concept is the non-uniform discrete Fourier transform (NDFT) method. The NDFT is obtained by sampling at non-uniformly distributed frequency points. However, for large samples of data, NDFT results in ill-conditioned calculations. For further details of NDFT, please see
[3] “Non-Uniform Discrete Fourier Transform and its Signal Processing Applications” by S. Bagchi and S. K. Mitra, Kluwer Academic Publishers, Norwell Mass., 1998, which is incorporated herein by reference.
In the prior art, it is well known that a large number of multiplications and additions are required for the calculation of the DFT. For example, if N=1024, then approximately one million complex multiplications and one million complex additions are necessary. In practice, the DFT is evaluated using a fast Fourier transform (FFT) algorithm, which requires on the order of (N log2 N)/2 multiplications. This is a significant decrease in the N2 multiplications required by the brute force approach. There are different versions of the FFT algorithm. An in depth treatment of the prior art FFT technology can be found in the following publications:
[4] “The Fast Fourier Transform and Its Applications” by E. O. Brigham, Prentice Hall, Englewood Cliffs, N.J., 1988, and
[5] “Handbook of Real-Time Fast Fourier Transforms” by W. W. Smith and J. M. Smith, IEEE Press, Piscataway, N.J., 1995, which are incorporated herein by reference.
For patents of interest concerning the prior art scalar-valued DFT and IDFT methods and the associated FFT technology, please see
U.S. Pat. No. 3,617,720 entitled “Fast Fourier Transform Using Hierarchical Store”, issued Nov. 2, 1971 to W. M. Gentleman;
U.S. Pat. No. 3,965,342 entitled “Digital FFT Processor Using Random Access Memory”, issued Jun. 22, 1976 to J. N. Constant;
U.S. Pat. No. 4,999,799 entitled “Signal Processing Apparatus for Generating a Fourier Transform”, issued Mar. 12, 1991 to D. W. Tufts;
U.S. Pat. No. 6,356,926 entitled “Device and Method for Calculating FFT”, issued Mar. 12, 2002 to T. Andre, and
U.S. Pat. No. 6,430,587 entitled “Method and Apparatus for FFT Computation”, issued Aug. 6, 2002 to A. Orling.
All of the above patents are incorporated herein by reference.
FIG. 1 is a graphic representation of a prior art FFT implementation with four data values x[0]-x[3] in the input column 10 and four data values f[0]-f[3] in the output column 15. This particular implementation approach is known as the decimation-in-time FFT method. FIG. 2 shows a recurring group of decimation-in-time operations referred to as a butterfly system. Observe that a typical prior art FTT implementation is composed of a series of scalar-valued butterfly systems. In the example shown in FIG. 2, the butterfly system has two scalar values x[0] and x[1] in the input column 20 and two scalar values f[0] and f[1] in the output column 25. Therefore, this system is called a radix-2 FFT algorithm.
The scalar-valued DFT expression (see Eq.7) defines how time-domain input samples are related to the frequency-domain information. The N-point scalar-valued DFT of a finite-duration signal with length N is equal to the Fourier transform of the signal at frequencies
                              f          k                =                                            k              N                        ⁢                                                  ⁢            0                    ≤          k          ≤                      N            -            1                                              (        16        )            
Clearly, the scalar-valued DFT can only compute as many points in the frequency spectrum as there are available sample points. In other words, the N-point scalar-valued DFT of a discrete-time signal corresponds to a uniform sampling of the Fourier transform at N equidistant frequency-domain points. Due to this fact, the scalar-valued DFT exhibits a rigid structure when it comes to the frequency spacing. What is needed is a new DFT/FFT method that has flexibility in specifying the frequency domain parameters.
Without exception, the prior art DFT and the associated FFT technology are based on scalar-valued transform algorithms operating on scalar-valued signals and variables. However, most of the practical dynamic systems (e.g. communications and control systems) involve multiple inputs and multiple outputs (MIMO). Consider, for example, multiple transmit and multiple receive antenna elements in a wireless MIMO communications system. These systems are modeled via vector and matrix variables with dimensions in the order of several thousands. In order to analyze and synthesize MIMO systems, there is a need for a matrix-valued DFT/FFT algorithm that operates on vector and matrix-valued signals, functions and variables.
The present invention overcomes the aforementioned difficulties and limitations of the scalar-valued DFT/FFT technology and offers an original and comprehensive solution by providing a matrix-valued framework. This new platform yields matrix-valued time-to-frequency domain transformation methods and algorithms resulting in a new class of matrix-valued devices and apparatus. Further objects and advantages of the present invention will become apparent from a consideration of the figures and ensuing description.